package com.linran.structure_algorithm.算法.lesson3_查找;

import java.util.Arrays;

/**
 * 斐波那契(黄金分割算法)
 */
public class FibonacciSearch {
    public static void main(String[] args) {
        int[] arr = new int[]{1, 2, 3, 4, 5, 6, 7, 8, 9};
        int i = fibonacciSearch(arr, 9);
        System.out.println(i + ":" + arr[i]);
    }

    /*需要使用到斐波那契数列*/
    public static int fibonacciSearch(int[] arr, int targetValue) {
        // 1：构建斐波那契数列
        int[] fiboArray = buildFiboArray(arr.length);

        // 2：计算数据长度对应斐波那契数列元素, fiboArray[k] >= arr.length
        int k = 0;
        while (fiboArray[k] < arr.length) {
            k++;
        }

        // 3：对数据进行填充
        int[] temp = Arrays.copyOf(arr, fiboArray[k]);
        for (int i = arr.length; i < fiboArray[k]; i++) {
            // 填充最大数
            temp[i] = arr[arr.length - 1];
        }

        // 4：对区间不断分割
        int left = 0;
        int right = temp.length - 1;
        while (left <= right && k >= 0) {
            // 计算中间位置
            int mid = left + fiboArray[k - 1] - 1;

            // 对三种情况分别处理
            // 目标值搜索成功
            if (temp[mid] == targetValue) {
                // 如果mid比原始数据长度大，则说明mid位置为填充的元素
                return Math.min(mid, arr.length - 1);
            }
            // 目标值在中间值左边，更新右边界
            else if (temp[mid] > targetValue) {
                //k--说明
                //全部元素=前面的元素＋后边元素
                //f[k] = f[k-1] +f[k-2]
                //因为前面有f[k-1]个元素,所以可以继续拆分f[k-1] = f[k-2] + f[k-3]
                //即在f[k-1]的前面继续查找k--
                //即下次循环mid = f[k-1-1]-1
                right = mid - 1;
                k--;
            }
            // 目标值在中间值右边，更新左边界
            else {
                // 为什么是k -=2/说明
                //1.全部元素=前面的元素＋后边元素
                //2.f[k] = f[k-1] + f[k-2]
                //3.因为后面我们有f[k-2]所以可以继续拆分f[k-1] = f[k-3] + f[k-4]
                //4.即在f[k-2]的前面进行查找k -=2
                //5.即下次循环mid = f[k - 1 - 2] - 1
                left = mid + 1;
                k -= 2;
            }
        }
        // 搜索失败
        return -1;
    }

    private static int[] buildFiboArray(int max) {
        int[] arr = new int[max];
        arr[0] = 1;
        arr[1] = 1;
        for (int i = 2; i < max; i++) {
            arr[i] = arr[i - 1] + arr[i - 2];
        }
        return arr;
    }
}
